package liecai_class.day03;

import java.util.Arrays;

/**
 * 快速排序
 *
 * 基于二分法, 对冒泡排序进行优化
 * 主要思路是: 确立一个基数, 将小于基数的数放到左边, 大于的放到右边
 * 在对基数左右两边的数进行同样操作的排序
 * 重复上述过程直到排序完成
 *
 * 优势: 基数固定之后就不再参与后续排序, 提高了排序的效率
 */
public class ArraySort05 {
    public static void main(String[] args) {
        int[] arr = {5,3,7,1,9,4,2,8,6};
        System.out.println("数组: "+Arrays.toString(arr));
        quickSort(arr,0,arr.length-1);
        System.out.println("排序后: "+Arrays.toString(arr));

    }
    private static void quickSort(int[] arr, int low, int high){
        //
        if (low>=high)
            return;

        //定义变量存储最小索引位的数据
        int temp = arr[low];

        int left = low;
        int right = high;

        while (right>left){
            //利用两个游标, 找到当前数据应该在的位置
            while (right>left && arr[right]>=temp){
                right--;
            }

            while (right>left && arr[left]<=temp){
                left++;
            }

            if (left<right){
                swap(arr,left,right);
            }
        }
        arr[low] = arr[left];
        arr[left] = temp;

        quickSort(arr,low,left-1);
        quickSort(arr,right+1,high);

    }

    private static void swap(int[] arr, int x, int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}
